//#ifdef __CS267_COMMON_H__
//#define __CS267_COMMON_H__

inline int min( int a, int b ) { return a < b ? a : b; }
inline int max( int a, int b ) { return a > b ? a : b; }

//
//  saving parameters
//
const int NSTEPS = 1000;
const int SAVEFREQ = 10;



//
// particle data structure
//
typedef struct 
{
  double x;
  double y;
  double vx;
  double vy;
  double ax;
  double ay;
} particle_t;


//
//  timing routines
//
double read_timer( );

//
//  simulation routines
//
void set_size( int n );
void init_particles( int n, particle_t *p );
void apply_force( particle_t &particle, particle_t &neighbor );
void move( particle_t &p );

//
//  I/O routines
//
FILE *open_save( char *filename, int n );
void save( FILE *f, int n, particle_t *p );

//
//  argument processing routines
//
int find_option( int argc, char **argv, const char *option );
int read_int( int argc, char **argv, const char *option, int default_value );
char *read_string( int argc, char **argv, const char *option, char *default_value );


//	Box data structure
//	This structure is used to implement the fast multipole method algorithm.
//	Each box contains a index in terms of (x, y). 
//	Element vector has a list of particles.
//	Parent pair is the coordinate for parent box.
//	Children array contains 4 coordinates of the sub boxes when the current box is splitted.
//	Neighbor vector contains all coordinates of the neighbor box of the current box.
//	Interacton list contains all boxes the current box is interacting with.
//	Level indicates which level of the index tree this box belongs to.
//	cmx and cmy indicate the mass center coordinates. 
//	tmass indicates the mass of all particles in the box. 
#include <list>
#include <vector>
using namespace std;
struct	box
{
	double x1, x2, y1, y2;			// Coordinates of the box

	particle_t box_particle;

	double cmx, cmy;				// Center of mass coordinates for the box
	double tmass;					// Total mass of all the particles
	pair<int, int> index;
	vector<int> element;
	pair<int, int> parent;
	pair<int, int> children[4];
	int level;
	vector< pair<int, int> > neighbor;
	vector< pair<int, int> > interaction_list;

	void init(double xi, double xe, double yi, double ye)
	{
		x1 = xi;
		x2 = xe;
		y1 = yi;
		y2 = ye;
	}

	void calculate_cm(particle_t *particles)
	{
		// Source: comology.ppt page: 13
		// Calculating center of mass for the box
		double tmpx = 0;
		double tmpy = 0;
		for(int i = 0; i < element.size(); i++)
		{
			tmpx += (0.01 * particles[element[i]].x);
			tmpy += (0.01 * particles[element[i]].y);
		}
		cmx = tmpx / tmass;	// Center of mass x coordiante
		cmy = tmpy / tmass; // Center of mass y coordinate
	}

	void add_new(int index)
	{
		element.push_back(index);
		tmass += 0.01;	// In common.cpp mass is defined as 0.01
	}

	void set_children(int cidx, int x, int y)
	{
		children[cidx].first = x;
		children[cidx].second = y;
	}

	void set_neighbor(int x, int y)
	{
		pair<int, int> pair(x, y);
		neighbor.push_back(pair);
	}
	
	void remove_neighbor(int x, int y)
	{
		for(vector< pair<int, int > >::iterator i = neighbor.begin(); i != neighbor.end(); i++)
		{
			if(x == (*i).first && y == (*i).second)
			{
				neighbor.erase(i);
				return;
			}
		}
	}

	void set_parent(int x, int y)
	{
		parent.first = x;
		parent.second = y;
	}

	void set_interact(int x, int y)
	{
		pair<int, int> pair(x, y);
		interaction_list.push_back(pair);
	}

	int get_size()
	{
		return element.size();
	}

};

//	Special box structure for MPI
//	Instead of having indexes of the particles, the mpi version box contains the copy
//	of actucal particles.
//	Except this, every other parameters is the same the normal box structure.
struct	mp_box
{
	double x1, x2, y1, y2;			// Coordinates of the box

	particle_t box_particle;

	double cmx, cmy;				// Center of mass coordinates for the box
	double tmass;					// Total mass of all the particles
	pair<int, int> index;
	vector<particle_t> element;
	pair<int, int> parent;
	pair<int, int> children[4];
	int level;
	vector< pair<int, int> > neighbor;
	vector< pair<int, int> > interaction_list;

	void init(double xi, double xe, double yi, double ye)
	{
		x1 = xi;
		x2 = xe;
		y1 = yi;
		y2 = ye;
	}

	void calculate_cm()
	{
		// Source: comology.ppt page: 13
		// Calculating center of mass for the box
		double tmpx = 0;
		double tmpy = 0;
		for(int i = 0; i < element.size(); i++)
		{
			tmpx += (0.01 * element[i].x);
			tmpy += (0.01 * element[i].y);
		}
		cmx = tmpx / tmass;	// Center of mass x coordiante
		cmy = tmpy / tmass; // Center of mass y coordinate
	}

	void add_new(particle_t index)
	{
		element.push_back(index);
		tmass += 0.01;	// In common.cpp mass is defined as 0.01
	}

	void set_children(int cidx, int x, int y)
	{
		children[cidx].first = x;
		children[cidx].second = y;
	}

	void set_neighbor(int x, int y)
	{
		pair<int, int> pair(x, y);
		neighbor.push_back(pair);
	}
	
	void remove_neighbor(int x, int y)
	{
		for(vector< pair<int, int > >::iterator i = neighbor.begin(); i != neighbor.end(); i++)
		{
			if(x == (*i).first && y == (*i).second)
			{
				neighbor.erase(i);
				return;
			}
		}
	}

	void set_parent(int x, int y)
	{
		parent.first = x;
		parent.second = y;
	}

	void set_interact(int x, int y)
	{
		pair<int, int> pair(x, y);
		interaction_list.push_back(pair);
	}

	int get_size()
	{
		return element.size();
	}

};

// apply_force_double() works just like apple_force(), except
// that is applies the force in both directions
void apply_force_double( particle_t &particle, particle_t &neighbor );
// Initializes the world root box
void init_world(box *world);
// Goes through a 2 dimensional array and creates an array with boxes
// in each position of the array
void initializations(box ***boxes, int target_level);
// This function gets a box
// and creates and initializes its children 
// and sets references the neighbor boxes
void split(box &b, particle_t *particles, box ***boxes, int x, int y);
// This function takes a box and sorts its particles to its children
void sort_elements(box &b, particle_t *particles, box ***boxes, int x, int y);
// This function goes through the boxes between box (x, y) and box (x2, y2)
// and sorts the particles in those boxes to their children
void assign_elements(box ***boxes, particle_t *particles, int level, int depth_level, int x, int y, int x2, int y2);
// Checks if two boxes are next to eachother/neighbors by
// checking the difference in index between them
int check_neighbor(box &box1, box &box2);
// This is Fast Multipole Method
void fmm(box ***boxes, particle_t *particles, int depth_level, vector < vector < pair <int, int> > > &box_list);
// This is Fast Multipole Method
// This version uses an older version which traverses through the boxes
// instead of going through the box_list like the other fmm versions do.
// This is because we concluded that changing this version to the same one 
// as the other would result in too many changes which would be requerd in
// openmp.cpp and the gain would be too little
void omp_fmm(box ***boxes, particle_t *particles, int level, int x, int y, int x2, int y2);
// This function goes through all of the boxes between box (x, y) and box(x2, y2)
// each box gets split (gets children initialised, assigned, etc...)
// after all of the boxes have been created and initialized
// neighbors are assigned, this is done after, and not during the same process
// because we must ensure all of the boxes actually are assigned properly on all of the 
// layers
void build_tree(box ***boxes, particle_t *particles, int level, int depth_level, int x, int y, int x2, int y2);
// This function will take a box and add all of its children
// that are at the bottom level to the box_list
void find_bottom_box(box &b, box ***boxes, vector< vector< pair < int, int > > >& box_list, int depth_level, int x, int y);

// Functions for MPI version
// They have their own version because they use mp_box instead of box
// This is because mp_box.element list holds actual particles
// while box.element list hold index values of particles

// mp_save() is just like save() except it takes particles 
// as a vector instead of an array 
void mp_save( FILE *f, int n, vector< particle_t > &p );
void mp_apply_force_pb(particle_t &particle, mp_box &box);
void mp_init_world(mp_box *world);
void mp_initializations(mp_box ***boxes, int target_level);
void mp_split(mp_box &b, mp_box ***boxes, int x, int y);
void mp_sort_elements(mp_box &b, mp_box ***boxes, int x, int y);
void mp_assign_elements(mp_box ***boxes, int level, int depth_level, int x, int y, int x2, int y2);
void mp_find_bottom_box(mp_box &b, mp_box ***boxes, vector< vector< pair < int, int > > >& box_list, int depth_level, int x, int y);
int mp_check_neighbor(mp_box &box1, mp_box &box2);
void mp_fmm(mp_box ***boxes,  int depth_level, vector < vector < pair <int, int> > > &box_list);
void mp_build_tree(mp_box ***boxes, int level, int depth_level, int x, int y, int x2, int y2);


//#endif
